package com.lyj.sc.dynamicProgramming.test20220727;

/**
 * @program: code-random
 * @description:
 * @author: lyj
 * @create: 2022-07-27 13:01
 * @version: 1.0
 * @Modifier By:
 **/
public class Solution {
    public int uniquePaths(int m, int n) {
        //1.定义dp数
        int [][] dp = new int[m][n];
        //2.递推公式
        //dp[i][j]=dp[i-1][j]+dp[i][j];
        //3.初始化
        for (int i = 0; i < m; i++) {
            dp[i][0]=1;
        }
        for (int j = 0; j < n; j++) {
            dp[0][j]=1;
        }
        //4.循环遍历
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j]=dp[i-1][j]+dp[i][j];
            }
        }
        return dp[m-1][n-1];
    }
}
